package internal.insertion;

/**
 * @描述：希尔排序，扩大步长的直接插入排序
 * @思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
 * @适用场合：Shell排序是通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数，其中Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起快速排序，归并排序，堆排序慢很多。但shell算法比较简单，特别适合数据量在5000以下且性能要求不是很高的场合。
 * @作者：hongxingfan
 * @时间：2014年9月4日 下午6:11:53
 */
public class ShellInsertionSort {

    public static void main(String[] args) {
        int[] datas = { 9, 4, 1, 8, 7, 5, 2, 0, 3, 4, 6 };

        // 带有步长的插入排序
        shellSort(datas);

        // 输出结果
        for (int data : datas)
            System.out.print(data + " ");
        System.out.println();
    }

    public static void shellSort(int[] datas) {
        // 步长的定义没有一个最好的方法
        int nk = datas.length / 2;
        while (nk >= 1) {
            shellInsertionSort(datas, nk);
            nk /= 2;
        }
    }

    // 增大步长的插入排序
    public static void shellInsertionSort(int[] datas, int nk) {
        for (int i = nk; i < datas.length; i++) {
            int tmp = datas[i];
            int j = i - nk; // 将插入排序中变量1改成nk就可以
            while (j >= 0) {
                if (datas[j] > tmp) {
                    datas[j + nk] = datas[j];
                    j -= nk;
                } else
                    break;
            }
            datas[j + nk] = tmp;
        }
    }
}
